|
In the mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar undirected graph with 5 vertices and 6 edges.〔ISGCI: Information System on Graph Classes and their Inclusions. "(List of Small Graphs )".〕 It can be constructed by joining 2 copies of the cycle graph ''C''3 with a common vertex and is therefore isomorphic to the friendship graph ''F''2. The butterfly Graph has diameter 2 and girth 3, radius 1, chromatic number 3, chromatic index 4 and is both Eulerian and unit distance. It is also a 1-vertex-connected graph and a 2-edge-connected graph. There are only 3 non-graceful simple graphs with five vertices. One of them is the butterfly graph. The two others are cycle graph ''C''5 and the complete graph ''K''5. ==Bowtie-free graphs== A graph is bowtie-free if it has no butterfly as an induced subgraph. The triangle-free graphs are bowtie-free graphs, since every butterfly contains a triangle. In a ''k''-vertex-connected graph, and edge is said ''k''-contractible if the contraction of the edge results in a ''k''-connected graph. Ando, Kaneko, Kawarabayashi and Yoshimoto proved that every ''k''-vertex-connected bowtie-free graph has a ''k''-contractible edge.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「butterfly graph」の詳細全文を読む スポンサード リンク
|